var sudoku;

$(document).on("pagecreate", function(event) {
	if ($("#text") && $("#loader")) {
		sudoku = new Sudoku();
		sudoku.html();
	}
});

function createTable() {
	var input = document.getElementById("text");
	var inputNumbers = input.value.replace(/\D/g, "").substring(0, 81);
	var reset = false;
	for (var index = inputNumbers.length; index < 81; ++index) {
		if (sudoku.cells[index].value !== 0) {
			reset = true;
			sudoku = new Sudoku();
			break;
		}
	}
	for (index = 0; index < inputNumbers.length; ++index) {
		var inputNumber = Number(inputNumbers.charAt(index));
		if (reset) {
			sudoku.cells[index].setValue(inputNumber);
			continue;
		}
		var sudokuNumber = sudoku.cells[index].value;
		if (inputNumber === sudokuNumber) {
			continue;
		}
		if (sudokuNumber === 0) {
			sudoku.cells[index].setValue(inputNumber);
		} else {
			reset = true;
			index = -1;
			sudoku = new Sudoku();
			continue;
		}
	}
	index = ~~((inputNumbers.length - 1) * 4 / 3 + 1);
	inputNumbers = sudoku.toString().substring(0, index);
	if (input.value !== inputNumbers) {
		input.value = inputNumbers;
	}
	if (reset) {
		sudoku.clear();
	}
	sudoku.html();
}

function solve() {
	if (!sudoku.solve()) {
		alert("Cannot solve!");
	}
	sudoku.html();
}

function Sudoku() {
	this.cells = [];
	this.row = [];
	this.col = [];
	this.box = [];

	for (var i = 0; i < 9; ++i) {
		this.row[i] = new Group("row", i);
		this.col[i] = new Group("col", i);
		this.box[i] = new Group("box", i);
	}

	for (i = 0; i < 81; ++i) {
		var r = ~~(i / 9);
		var c = i % 9;
		var b = ~~(r / 3) * 3 + ~~(c / 3);
		this.cells[i] = new Cell(this.row[r], this.col[c], this.box[b]);
	}
}

Sudoku.prototype.html = function() {
	var string = "<table class='table'>";
	for (var i = 0; i < 9; ++i) {
		string += "<tr>";
		for (var j = 0; j < 9; ++j) {
			var cell = this.row[i].cells[j];
			string += "<td class='" + cell.highlight + "'>" + cell.html() + "</td>";
		}
		string += "</tr>";
	}
	this.clear();
	document.getElementById("loader").innerHTML = string;
};

Sudoku.prototype.clear = function() {
	this.cells.forEach(function(cell) {
		cell.highlight = cell.box.number % 2 === 0 ? 'even' : 'odd';
		cell.removed = [];
	});
};

Sudoku.prototype.toString = function() {
	var string = "";
	for (var i = 0; i < 81; ++i) {
		if (i % 9 === 0) {
			string += ";";
		} else if (i % 3 === 0) {
			string += ",";
		}
		string += this.cells[i].value;
	}
	return string.substring(1);
};

Sudoku.prototype.solve = function() {
	var found = false;
	found = found || this.updateSingleCandidate();
	found = found || this.updateUniqueCandidate();
	found = found || this.findNakedCandidates(2);
	found = found || this.findNakedCandidates(3);
	found = found || this.findNakedCandidates(4);
	found = found || this.findLockedCandidate();
	found = found || this.findHiddenCandidates(2);
	found = found || this.findHiddenCandidates(3);
	found = found || this.findHiddenCandidates(4);
	return found;
};

Sudoku.prototype.updateSingleCandidate = function() {
	return this.cells.some(function(cell) {
		if (cell.candidates.length === 1) {
			cell.setValue(cell.candidates[0]);
			return true;
		}
		return false;
	});
};

Sudoku.prototype.updateUniqueCandidate = function() {
	var found = false;
	found = found || this.row.some(function(group) {
		return group.updateUniqueCandidate();
	});
	found = found || this.col.some(function(group) {
		return group.updateUniqueCandidate();
	});
	found = found || this.box.some(function(group) {
		return group.updateUniqueCandidate();
	});
	return found;
};

Sudoku.prototype.findNakedCandidates = function(n) {
	var found = false;
	found = found || this.row.some(function(group) {
		return group.findNakedCandidates(n);
	});
	found = found || this.col.some(function(group) {
		return group.findNakedCandidates(n);
	});
	found = found || this.box.some(function(group) {
		return group.findNakedCandidates(n);
	});
	return found;
};

Sudoku.prototype.findHiddenCandidates = function(n) {
	var found = false;
	found = found || this.row.some(function(group) {
		return group.findHiddenCandidates(n);
	});
	found = found || this.col.some(function(group) {
		return group.findHiddenCandidates(n);
	});
	found = found || this.box.some(function(group) {
		return group.findHiddenCandidates(n);
	});
	return found;
};

Sudoku.prototype.findLockedCandidate = function() {
	for (var c = 1; c <= 9; ++c) {
		for (var i = 0; i < 9; ++i) {
			if (this.row[i].findLockedCandidate(c)
			|| this.col[i].findLockedCandidate(c)) {
				return true;
			}
		}
	}
	return false;
};

function Group(type, number) {
	this.type = type;
	this.number = number;
	this.cells = [];
}

Group.prototype.toString = function(candidate) {
	return this.type + " " + this.number;
};

Group.prototype.remove = function(candidate) {
	var found = false;
	var duplicates = 0;
	for (var i = 0; i < this.cells.length; ++i) {
		var cell = this.cells[i];
		found |= cell.remove(candidate);
		if (cell.value === candidate) {
			++duplicates;
		}
	}
	if (duplicates > 1) {
		this.highlight("error");
	}
	return found;
};

Group.prototype.highlight = function(style) {
	this.cells.forEach(function(cell) {
		cell.highlight += " " + style;
	});
};

Group.prototype.getCells = function(candidate) {
	var array = [];
	for (var i = 0; i < this.cells.length; ++i) {
		var cell = this.cells[i];
		if (cell.candidates.indexOf(candidate) > -1) {
			array.push(cell);
		}
	}
	return array;
};

Group.prototype.updateUniqueCandidate = function() {
	for (var i = 1; i <= 9; ++i) {
		var cell = this.getCells(i);
		if (cell.length === 1) {
			this.highlight(this.type);
			cell[0].setValue(i);
			return true;
		}
	}
	return false;
};

Group.prototype.getCombination = function(n) {
	var numberCombinations = getCombination(n, 9);
	var cellCombinations = [];
	NEXT_COMBINATION:
	for (var i = 0; i < numberCombinations.length; ++i) {
		var numberCombination = numberCombinations[i];
		var cellCombination = [];
		for (var j = 0; j < n; ++j) {
			var cell = this.cells[numberCombination[j]];
			if (cell.value === 0) {
				cellCombination.push(cell);
			} else {
				continue NEXT_COMBINATION;
			}
		}
		cellCombinations.push(cellCombination);
	}
	return cellCombinations;
};

Group.prototype.findNakedCandidates = function(n) {
	var found = false;
	var combinations = this.getCombination(n);
	NEXT_COMBINATION:
	for (var i = 0; i < combinations.length; ++i) {
		var combination = combinations[i];
		var common = {};
		for (var j = 0; j < n; ++j) {
			var candidates = combination[j].candidates;
			if (candidates.length > n) {
				continue NEXT_COMBINATION;
			}
			for (var k = 0; k < candidates.length; ++k) {
				common[candidates[k]] = true;
			}
		}
		var candidates = [];
		for (var k in common) {
			if (common.hasOwnProperty(k)) {
				candidates.push(k);
			}
		}
		if (candidates.length !== n) {
			continue;
		}
		NEXT_CELL:
		for (var j = 0; j < 9; ++j) {
			var cell = this.cells[j];
			if (cell.value != 0) {
				continue;
			}
			for (var k = 0; k < n; ++k) {
				if (cell === combination[k]) {
					continue NEXT_CELL;
				}
			}
			found = found || cell.remove(candidates);
		}
	}
	return found;
};

Group.prototype.findHiddenCandidates = function(n) {
	var found = false;
	var candidates = [];
	for (var i = 1; i <= 9; ++i) {
		var length = this.getCells(i).length;
		if (length > 0 && length <= n) {
			candidates.push(i);
		}
	}
	if (candidates.length < n) {
		return false;
	}
	getCombination(n, candidates.length).some(function(combination) {
		var list = [];
		for (var i = 0; i < combination.length; ++i) {
			var cellList = this.getCells(candidates[combination[i]]);
			cellList.forEach(function(cell) {
				if (list.indexOf(cell) === -1) {
					list.push(cell);
				}
			});
		}
		if (list.length != n) {
			return false;
		}
		list.forEach(function(cell) {
			cell.candidates.forEach(function(candidate) {
				if (candidates.indexOf(candidate) === -1) {
					cell.remove(candidate);
				}
			});
		});
	}, this);
	return found;
};

Group.prototype.findLockedCandidate = function(n) {
	var boxes = [];
	var match = this.getCells(n);
	match.forEach(function(cell) {
		if (boxes.indexOf(cell.box) === -1) {
			boxes.push(cell.box);
		}
	});
	if (boxes.length == 0) {
		return false;
	}
	if (boxes.length == 1) {
		var found = false;
		boxes[0].getCells(n).forEach(function(cell) {
			if (match.indexOf(cell) === -1) {
				found = true;
				cell.remove(n);
			}
		});
		if (found) {
			this.highlight(this.type);
			match.forEach(function(cell) {
				cell.highlight += " reference";
			});
		}
		return found;
	}
	return boxes.some(function(box) {
		var boxCells = box.getCells(n);
		var found = boxCells.every(function(cell) {
			return match.indexOf(cell) !== -1;
		});
		if (found) {
			match.forEach(function(cell) {
				if (boxCells.indexOf(cell) === -1) {
					cell.remove(n);
				} else {
					cell.highlight += " reference";
				}
			});
			this.highlight(this.type);
		}
		return found;
	}, this);
};

function Cell(row, col, box) {
	this.row = row;
	this.col = col;
	this.box = box;
	row.cells[row.cells.length] = this;
	col.cells[col.cells.length] = this;
	box.cells[box.cells.length] = this;
	this.value = 0;
	this.candidates = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ];
	this.highlight = box.number % 2 ? 'even' : 'odd';
	this.removed = [];
}

Cell.prototype.setValue = function(value) {
	if (value === 0) {
		return;
	}
	this.value = value;
	this.candidates = [];
	this.highlight += " reference";
	this.row.remove(value);
	this.col.remove(value);
	this.box.remove(value);
};

Cell.prototype.remove = function(candidates) {
	var index;
	var found = false;
	if (candidates instanceof Array) {
		for (var i = 0; i < candidates.length; ++i) {
			index = this.candidates.indexOf(candidates[i]);
			if (index !== -1) {
				this.candidates.splice(index, 1);
				this.removed.push(candidates);
				found = true;
			}
		}
	} else {
		index = this.candidates.indexOf(candidates);
		if (index !== -1) {
			this.candidates.splice(index, 1);
			this.removed.push(candidates);
			found = true;
		}
	}
	return found;
};

Cell.prototype.toString = function() {
	var string = "(" + this.row + ", " + this.col + ", " + this.box + ") ";
	string += this.value === 0 ? this.candidates : this.value;
	return string;
};

Cell.prototype.html = function() {
	if (this.value !== 0) {
		return this.value;
	}
	var string = "<table>";
	for (var i = 1; i <= 9; ++i) {
		if (i % 3 === 1) {
			string += "<tr>";
		}
		if (this.candidates.indexOf(i) !== -1) {
			string += "<td>" + i + "</td>";
		} else if (this.removed.indexOf(i) !== -1) {
			string += "<td class='removed'>" + i + "</td>";
		} else {
			string += "<td>&nbsp;</td>";
		}
		if (i % 3 === 0) {
			string += "</tr>";
		}
	}
	string += "</table>";
	return string;
};

function getCombination(k, n) {
	if (k < 1 || k > n) {
		console.error("Invalid combination (" + k + ", " + n + ")");
		return;
	}
	var combination = [];
	if (k === 1) {
		for (var i = 0; i < n; ++i) {
			combination.push([ i ]);
		}
		return combination;
	}
	var priorCombination = getCombination(k - 1, n);
	for (var i = 0; i < priorCombination.length; ++i) {
		var list = priorCombination[i];
		for (var j = list[k - 2] + 1; j < n; ++j) {
			combination.push(list.concat([ j ]));
		}
	}
	return combination;
}
